/* **************************************************************** /

Most of this file was taken from:
 http://cprogramminglanguage.net/binary-heap-c-code.aspx

Added Resize methods and modified the heap to use proc_info structures 

*******************************************************************/

#include "binheap.h"
#include <stdlib.h>
#include <stdio.h>
#include "includes.h"

#define MinPQSize (5)
#define MinData MinElem

struct proc_info *MinElem;
struct proc_info MinProc;

struct HeapStruct {
    int Capacity;
    int Size;
    ElementType *Elements;
};

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    MinProc.time_remaining = -1;
    MinElem = &MinProc;

    /*  if (MaxElements < MinPQSize)*/
      /*printf("Priority queue size is too small"); */

    /* 3*/ H = malloc(sizeof ( struct HeapStruct));
    /* 4*/ if (H == NULL)
        /* 5*/ printf("Out of space!!!");

    /* Allocate the array plus one extra for sentinel */
    /* 6*/ H->Elements = malloc((MaxElements + 1)
            * sizeof ( ElementType));
    /* 7*/ if (H->Elements == NULL)
        /* 8*/ printf("Out of space!!!");

    /* 9*/ H->Capacity = MaxElements;
    /*10*/ H->Size = 0;
    /*11*/ H->Elements[ 0 ] = MinData;

    /*12*/ return H;
}

/* END */

void MakeEmpty(PriorityQueue H) {
    H->Size = 0;
}

/* H->Element[ 0 ] is a sentinel */

void Insert(ElementType X, PriorityQueue *Q) {
    int i;
    PriorityQueue H;

    if (IsFull(*Q)) {
      Resize(Q);
    }

    H = *Q;

    for (i = ++H->Size; H->Elements[ i / 2 ]->time_remaining > X->time_remaining; i /= 2)
        H->Elements[ i ] = H->Elements[ i / 2 ];
    H->Elements[ i ] = X;
}

/* END */


ElementType DeleteMin(PriorityQueue H) {
    int i, Child;
    ElementType MinElement, LastElement;

    /* 1*/ if (IsEmpty(H)) {
        /* 2*/ printf("Priority queue is empty");
        /* 3*/ return H->Elements[ 0 ];
    }
    /* 4*/ MinElement = H->Elements[ 1 ];
    /* 5*/ LastElement = H->Elements[ H->Size-- ];

    /* 6*/ for (i = 1; i * 2 <= H->Size; i = Child) {
        /* Find smaller child */
        /* 7*/ Child = i * 2;
        /* 8*/ if (Child != H->Size && H->Elements[ Child + 1 ]->time_remaining
                /* 9*/ < H->Elements[ Child ]->time_remaining)
            /*10*/ Child++;

        /* Percolate one level */
        /*11*/ if (LastElement->time_remaining > H->Elements[ Child ]->time_remaining)
            /*12*/ H->Elements[ i ] = H->Elements[ Child ];
        else
            /*13*/ break;
    }
    /*14*/ H->Elements[ i ] = LastElement;
    /*15*/ return MinElement;
}

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H))
        return H->Elements[ 1 ];
    printf("Priority Queue is Empty");
    return H->Elements[ 0 ];
}

int IsEmpty(PriorityQueue H) {
    return H->Size == 0;
}

int IsFull(PriorityQueue H) {
    return H->Size == H->Capacity;
}

void Destroy(PriorityQueue H) {
    free(H->Elements);
    free(H);
}

/* Accepts a pointer to a PQ, and resizes its Elements field */
void Resize(PriorityQueue *Q) {
  ElementType *Elements;
  int i, Capacity;

  /* Get old capacity */
  Capacity = (*Q)->Capacity;

  /* Double the element size field */
  Elements = malloc((Capacity * 2 + 1) * sizeof( ElementType ) );
  
  if (Elements == NULL) {
    printf("Out of space on malloc\n");
    exit(-1);
  }

  /* Copy the old elements which are already ordered */
  for(i = 0; i <= (*Q)->Size; i++) {
    Elements[ i ] = (*Q)->Elements[ i ];
  }

  /* Free old space */
  free((*Q)->Elements);

  /* Reassign elements */
  (*Q)->Elements = Elements;

  /* Rassign Capacity */
  (*Q)->Capacity = Capacity * 2;
}

#if 0

for (i = N / 2; i > 0; i--)
    PercolateDown(i);

#endif
